package com.kehao.leetcode.middle.tree_graph;

import org.junit.Test;

public class NumIslandsSolution {

    //使用深度优先搜索实现
    public int numIslands(char[][] grid) {
        boolean[][] isVisited = new boolean[grid.length][grid[0].length];
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visit(i,j,isVisited,grid)){
                    result++;
                }
            }
        }
        return result;
    }

    //使用并查集实现
    public int numIslands2(char[][] grid) {
        return 0;
    }

    private boolean visit(int i, int j, boolean[][] isVisited, char[][] grid) {
        if(!isVisited[i][j]&&grid[i][j]=='1'){
            isVisited[i][j]=true;
            if(i!=0) visit(i-1,j,isVisited,grid);
            if(j!=0)visit(i,j-1,isVisited,grid);
            if(i<grid.length-1) visit(i+1,j,isVisited,grid);
            if(j<grid[0].length-1) visit(i,j+1,isVisited,grid);
            return true;
        }
        return false;
    }


    @Test
    public void test01(){
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        System.out.println(numIslands(grid));
    }

    @Test
    public void test02(){
        char[][] grid = {
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        System.out.println(numIslands(grid));
    }


}
